package com.le.enhance.class5;

import org.junit.Test;

/**
 * 1. 判断二叉树是否是搜索二叉树
 */
public class Code_01_IsBST {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class ReturnType {
       public boolean isCBT;
       public int min;
       public int max;

        public ReturnType(boolean isCBT, int min, int max) {
            this.isCBT = isCBT;
            this.min = min;
            this.max = max;
        }
    }

    public static boolean isCBT(Node head){
        return process(head).isCBT;
    }

    public static ReturnType process(Node head){
        if (head == null){
            return new ReturnType(true,Integer.MAX_VALUE,Integer.MIN_VALUE);
        }

        ReturnType leftInfo = process(head.left);
        if (!leftInfo.isCBT){
            return new ReturnType(false,Integer.MAX_VALUE,Integer.MIN_VALUE);
        }

        ReturnType rightInfo = process(head.right);
        if (!rightInfo.isCBT){
            return new ReturnType(false,Integer.MAX_VALUE,Integer.MIN_VALUE);
        }

        if (leftInfo.max >= head.value){
            return new ReturnType(false,Integer.MAX_VALUE,Integer.MIN_VALUE);
        }
        if (rightInfo.min <= head.value){
            return new ReturnType(false,Integer.MAX_VALUE,Integer.MIN_VALUE);
        }

        return new ReturnType(true,
                Math.min(Math.min(leftInfo.min, rightInfo.min),head.value),
                Math.max(Math.max(leftInfo.max, rightInfo.max),head.value)
        );
    }



    @Test
    public void testBST() {
        Node head = new Node(4);
        head.left = new Node(2);
        head.right = new Node(6);
        head.left.left = new Node(1);
        head.left.right = new Node(0);
        head.right.left = new Node(5);
        System.out.println(isCBT(head));

    }
}
